package main

import "fmt"

//type ListNode struct {
//	Val  int
//	Next *ListNode
//}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	// 创建一个哑节点作为新链表的头部
	dummy := &ListNode{}
	current := dummy

	// 遍历两个链表，按顺序合并节点
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			current.Next = list1
			list1 = list1.Next
		} else {
			current.Next = list2
			list2 = list2.Next
		}
		current = current.Next
	}

	// 如果一个链表遍历完了，直接接上另一个链表
	if list1 != nil {
		current.Next = list1
	} else {
		current.Next = list2
	}

	// 返回合并后的链表头节点
	return dummy.Next
}

// printList 打印链表
func printList(head *ListNode) {
	for head != nil {
		fmt.Print(head.Val, " ")
		head = head.Next
	}
	fmt.Println()
}

func main() {
	// 示例 1
	l1 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 4}}}
	l2 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}
	mergedList := mergeTwoLists(l1, l2)
	printList(mergedList) // 输出: 1 1 2 3 4 4

	// 示例 2
	l1 = nil
	l2 = nil
	mergedList = mergeTwoLists(l1, l2)
	printList(mergedList) // 输出: 空

	// 示例 3
	l1 = nil
	l2 = &ListNode{Val: 0}
	mergedList = mergeTwoLists(l1, l2)
	printList(mergedList) // 输出: 0
}
